package q0148;

/**
 * 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
 * <p>
 * 示例 1:
 * <p>
 * 输入: 4->2->1->3
 * 输出: 1->2->3->4
 * 示例 2:
 * <p>
 * 输入: -1->5->3->4->0
 * 输出: -1->0->3->4->5
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sort-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * <p>
 * <p>
 * 解题：题目要求了 nlogN 的时间复杂度
 * <p>
 * 1. 快排
 * 2. 归并
 * <p>
 * 本题解法使用归并算法
 *
 * @author fangjiaxiaobai@gmail.com
 * @version 1.0.0
 * @date 2020-05-26
 */
public class Solution2 {

    /**
     * 1. 快慢指针找中点
     * 1.1 奇数情况下,选择重点左侧的，
     * 1.2 偶数情况下，选择中点左侧,包括中点。
     * 2. 并
     *
     * @param head 头结点
     * @return 头结点
     */
    public ListNode sortList(ListNode head) {

        /// 判断结束条件
        if (head == null || head.next == null) {
            return head;
        }

        // 快慢指针找中点
        ListNode slow = head;
        ListNode fast = head.next;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 中间的节点，先暂时断开指针，用于归操作时候的结束条件判断
        ListNode middleTmpLinkNode = slow.next;
        slow.next = null;

        // 分别对已经断开的两段进行归操作
        ListNode leftNodes = sortList(head);
        ListNode rightNodes = sortList(middleTmpLinkNode);

        //2.并操作
        ListNode tempHeadNode = new ListNode(0);
        /// 记录返回的头指针,即 res->next
        ListNode res = tempHeadNode;

        while (leftNodes != null && rightNodes != null) {
            if (leftNodes.val < rightNodes.val) {
                tempHeadNode.next = leftNodes;
                leftNodes = leftNodes.next;
            } else {
                tempHeadNode.next = rightNodes;
                rightNodes = rightNodes.next;
            }
            tempHeadNode = tempHeadNode.next;
        }
        tempHeadNode.next = (leftNodes == null ? rightNodes : leftNodes);
        return res.next;
    }

    public static void main(String[] args) {
        ListNode n4 = new ListNode(4);
        ListNode n2 = new ListNode(2);
        ListNode n1 = new ListNode(1);
        ListNode n3 = new ListNode(3);

        n4.next = n2;
        n2.next = n1;
        n1.next = n3;

        ListNode listNode = new Solution2().sortList(n4);

        printNode(listNode);
    }

    private static void printNode(ListNode head) {
        while (null != head) {
            System.out.printf("%d\t", head.val);
            head = head.next;
        }
        System.out.println();
    }

}
